package com.itheima.leetcode.od.b.backtracking;

/**
 * (B卷,200分)- 最佳的出牌方法（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 手上有一副扑克牌，每张牌按牌面数字记分（J=11,Q=12,K=13，没有大小王)，出牌时按照以下规则记分：
 * <p>
 * 出单张，记牌面分数，例如出一张2，得分为2
 * 出对或3张，记牌面分数总和再x2，例如出3张3，得分为(3+3+3)x2=18
 * 出5张顺，记牌面分数总和再x2，例如出34567顺，得分为(3+4+5+6+7)x2=50
 * 出4张炸弹，记牌面分数总和再x3，例如出4张4，得分为4x4x3=48
 * 求出一副牌最高的得分数
 * <p>
 * 输入描述
 * <p>
 * 按顺序排好的一副牌，最少1张，最多15张。
 * 1-9输入为数字1-9，10输入为数字0，JQK输入为大写字母JQK.
 * 无需考虑输入非法的情况，例如输入字符不在[0-9JQK]范围或某一张牌超过4张
 * <p>
 * 输出描述
 * <p>
 * 最高的得分数
 * <p>
 * 备注
 * 积分规则中没有的出牌方式不支持，例如不支持3带1、4带2，不支持5张以上的顺，且10JQKA (0JQK1) 不算顺。
 * <p>
 * 用例
 * <p>
 * 输入	33445677
 * 输出	67
 * 说明
 * 出对3、对4、对7，单张5、6，得分为67;
 * <p>
 * 出34567顺，再出单张3、4、7，得分为64
 * <p>
 * 因此最高得分是按对出，可得到最高分67，输出结果67
 */
public class OptimalWayToPlayCards {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        System.out.println(getResult(sc.nextLine()));*/

        String input = "33445677";

        System.out.println(getResult(input));
    }

    // 保存最大分数
    static int max_score = 0;

    public static int getResult(String cards) {
        // 数组索引是牌面分数, 数组元素是牌面数量, 其中 0 索引不用
        int[] card_count = new int[14];

        // 统计各种牌的数量
        for (int i = 0; i < cards.length(); i++) {
            char card = cards.charAt(i);

            // 1-9输入为数字1-9，10输入为数字0，JQK输入为大写字母JQK
            // 1-9 牌面分数就是 1-9, 0的牌面分数是 10, J=11,Q=12,K=13, 可以发现牌面分数是连续的，可以和card_count数组的索引对应起来
            card_count[mapToNum(card)]++;
        }

        getMaxScore(card_count, cards.length(), 1, 0);

        return max_score;
    }

    // 牌大小 映射为 数值
    public static int mapToNum(char card) {
        switch (card) {
            case '0':
                return 10;
            case 'J':
                return 11;
            case 'Q':
                return 12;
            case 'K':
                return 13;
            default:
                return card - '0';
        }
    }

    /**
     * 获取最大分数
     *
     * @param card_count        各种牌的数量
     * @param unused_card_count 剩余牌的总数量
     * @param startIdx          从哪个位置开始选牌
     * @param score             此时已获得的总分数
     */
    public static void getMaxScore(int[] card_count, int unused_card_count, int startIdx, int score) {
        // 所有牌都打完了
        if (unused_card_count == 0) {
            // 则比较此时出牌策略获得的总分score，和历史最高分max_score，保留较大者
            max_score = Math.max(score, max_score);
            return;
        }

        // 没有可以出的牌，则继续递归到startIdx+1开始出牌
        if (card_count[startIdx] == 0) {
            getMaxScore(card_count, unused_card_count, startIdx + 1, score);
        }

        // 还有可以出的牌，则从startIdx开始出牌
        // 如果当前牌的数量至少1张
        if (card_count[startIdx] >= 1) {
            // 策略1、可以尝试出顺子，由于最大的顺子是9,10,J,Q,K,因此 i 作为顺子起始牌的话，不能超过9，且后续牌面 i+1, i+2, i+3, i+4 的数量都至少有1张
            if (startIdx <= 9
                    && card_count[startIdx + 1] >= 1
                    && card_count[startIdx + 2] >= 1
                    && card_count[startIdx + 3] >= 1
                    && card_count[startIdx + 4] >= 1) {
                card_count[startIdx] -= 1;
                card_count[startIdx + 1] -= 1;
                card_count[startIdx + 2] -= 1;
                card_count[startIdx + 3] -= 1;
                card_count[startIdx + 4] -= 1;
                // 顺子是5张牌，因此出掉顺子后，可用牌数量减少5张，总分增加 (i + (i+1) + (i+2) + (i+3) + (i+4)) * 2
                getMaxScore(card_count, unused_card_count - 5, startIdx, score + (5 * startIdx + 10) * 2);
                // 回溯
                card_count[startIdx] += 1;
                card_count[startIdx + 1] += 1;
                card_count[startIdx + 2] += 1;
                card_count[startIdx + 3] += 1;
                card_count[startIdx + 4] += 1;
            }

            // 策略2、出单张
            card_count[startIdx] -= 1;
            getMaxScore(card_count, unused_card_count - 1, startIdx, score + startIdx);
            card_count[startIdx] += 1;
        }

        // 如果当前牌的数量至少2张，那么可以出对子
        if (card_count[startIdx] >= 2) {
            card_count[startIdx] -= 2;
            getMaxScore(card_count, unused_card_count - 2, startIdx, score + startIdx * 2 * 2);
            card_count[startIdx] += 2;
        }

        // 如果当前牌的数量至少3张，那么可以出三张
        if (card_count[startIdx] >= 3) {
            card_count[startIdx] -= 3;
            getMaxScore(card_count, unused_card_count - 3, startIdx, score + startIdx * 3 * 2);
            card_count[startIdx] += 3;
        }

        // 当前当前牌的数量至少4张，那么可以出炸弹
        if (card_count[startIdx] >= 4) {
            card_count[startIdx] -= 4;
            getMaxScore(card_count, unused_card_count - 4, startIdx, score + startIdx * 4 * 3);
            card_count[startIdx] += 4;
        }
    }
}